This phase I and II study will determine the safety and toxicity of the chemotherapy regimen Adriamycin, Bleomycin, and Vincristine (ABV) for advanced AIDS-Related Kaposi's Sarcoma in combination with either dideoxyinosine (ddI0 or dideoxycitidine (ddC) at doses generally used in current treatment of IND studies.